package graphtheory.腐烂的橘子;

import java.util.ArrayDeque;
import java.util.Queue;

public class Solution {
    public int orangesRotting(int[][] grid) {
        int ans = 0;
        int fresh = 0;
        Queue<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                } else if (grid[i][j] == 1) {
                    fresh++;
                }
            }
        }
        if (fresh == 0 ){
            return 0;
        }
        int rLen = grid.length;
        int cLen = grid[0].length;
        while (!queue.isEmpty()) {
            int size = queue.size();
            ans++;
            for (int k = 0; k < size; k++) {
                int[] poll = queue.poll();
                int i = poll[0];
                int j = poll[1];
                if (i - 1 > -1 && grid[i - 1][j] == 1) {
                    fresh--;
                    grid[i - 1][j] = 2;
                    queue.offer(new int[]{i - 1, j});
                }
                if (i + 1 < rLen && grid[i + 1][j] == 1) {
                    fresh--;
                    grid[i + 1][j] = 2;
                    queue.offer(new int[]{i + 1, j});
                }
                if (j - 1 > -1 && grid[i][j - 1] == 1) {
                    fresh--;
                    grid[i][j - 1] = 2;
                    queue.offer(new int[]{i, j - 1});
                }
                if (j + 1 < cLen && grid[i][j + 1] == 1) {
                    fresh--;
                    grid[i][j + 1] = 2;
                    queue.offer(new int[]{i, j + 1});
                }
                if (fresh == 0) {
                    return ans;
                }
            }

        }
        return fresh == 0 ? ans : -1;
    }


    public static void main(String[] args) {
//        [[2,1,1],[1,1,0],[0,1,1]]
        Solution solution = new Solution();
        System.out.println(solution.orangesRotting(new int[][]{{2, 1, 1}, {1, 1, 0}, {0, 1, 1}}));
    }

}
